


#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    vector<int> searchRange1(vector<int>& nums, int target)
    {
        int sz = nums.size();

        if (0 == sz)
            return { -1, -1 };
        {
            int lf = 0, rg = sz - 1;

            while (lf <= rg)
            {
                int mid = lf + ((rg - lf) >> 1);

                if (nums[mid] > target)
                    rg = mid - 1;
                else if (nums[mid] < target)
                    lf = mid + 1;
                else
                {
                    int i = 0;

                    while (lf <= rg && nums[lf] != target)
                    {
                        ++lf;
                    }

                    while (lf <= rg && nums[rg] != target)
                    {
                        --rg;
                    }

                    return { lf, rg };
                }
            }

            return { -1, -1 };
        }
    }

    vector<int> searchRange2(vector<int>& nums, int target)
    {
        int sz = nums.size();

        if (0 == sz)
            return { -1, -1 };

        int lf = 0, rg = 0;
        int left = 0, right = sz - 1;

        while (left < right)
        {
            int mid = left + ((right - left) >> 1);

            if (nums[mid] > target)
                right = mid - 1;
            else if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid;
        }
        if (target == nums[left])
            lf = left;
        else
            return { -1, -1 };

        left = 0, right = sz - 1;
        while (left < right)
        {
            int mid = left + ((right - left + 1) >> 1);

            if (nums[mid] > target)
                right = mid - 1;
            else if (nums[mid] < target)
                left = mid + 1;
            else
                left = mid;
        }
        rg = left;

        return { lf, rg };
    }

    int searchInsert(vector<int>& nums, int target)
    {
        int lf = 0, rg = nums.size() - 1;

        while (lf <= rg)
        {
            int mid = lf + ((rg - lf) >> 1);

            if (target == nums[mid])
                return mid;
            else if (target > nums[mid])
                lf = mid + 1;
            else
                rg = mid - 1;
        }

        return lf;
    }

    vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
    {
        vector<int> v;
        v.reserve(1001);
        int hash1[1001] = { 0 }, hash2[1001] = { 0 };

        for (const auto& n : nums1)
        {
            hash1[n]++;
        }
        for (const auto& n : nums2)
        {
            hash2[n]++;
        }

        for (int i = 0; i < 1001; ++i)
        {
            if (hash1[i] && hash2[i])
                v.push_back(i);
        }

        return v;
    }

    int longestOnes(vector<int>& nums, int k)
    {
        int sz = nums.size();
        int lf = 0, rg = 0;
        int cnt = 0, maxlen = 0;

        while (rg < sz)
        {
            if (0 == nums[rg++])
                ++cnt;

            while (cnt > k)
            {
                if (0 == nums[lf++])
                    --cnt;
            }
            maxlen = max(maxlen, rg - lf);
        }

        return maxlen;
    }
};

void Test1()
{
    class B1
    {
    public:
        virtual void funcB1()
        {
            cout << "B1:virtual void funcB1()" << endl;
        }
    };

    class B2
    {
    public:
        virtual void funcB2()
        {
            cout << "B2:virtual void funcB2()" << endl;
        }
    };

    class D : public B1, public B2
    {
    public:
        virtual void funcB1()
        {
            cout << "D:virtual void funcB1()" << endl;
        }

        virtual void funcB2()
        {
            cout << "D:virtual void funcB2()" << endl;
        }

        virtual void func()
        {
            cout << "D:virtual void func2()" << endl;
        }
    };

    B1 b1;
    B2 b2;
    D d;
}

void Test2()
{
    class A
    {
    public:
        A() :m_iVal(0) { test(); }
        virtual void func() { std::cout << m_iVal << ' '; }
        void test() { func(); }

    public:
        int m_iVal;
    };

    class B : public A
    {
    public:
        B() { test(); }
        virtual void func()
        {
            ++m_iVal;
            std::cout << m_iVal << ' ';
        }
    };

    A* p = new B;
    p->test();   
}

void Test3()
{
    class A
    {
    public:
        virtual void f()
        {
            cout << "A::f()" << endl;
        }
    };

    class B : public A
    {
    private:
        virtual void f()
        {
            cout << "B::f()" << endl;
        }
    };

    A* pa = (A*)new B;
    pa->f();
}

void Test4(void)
{
    vector<int> v = { 0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1 };
    int k = 3;

    Solution().longestOnes(v, 3);
}

int main()
{
    //Test1();
    //Test2();
    //Test3();
    Test4();

	return 0;
}